package TextBinaryTree;

import java.util.*;


public class TextBinaryTree2 {
    static class TreeNode {
        public char val;
        public TreeNode left;//左孩子节点的引用
        public TreeNode right;//右孩子节点的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public TreeNode root;
    public TextBinaryTree.TreeNode createTree1() {
        TextBinaryTree.TreeNode A = new TextBinaryTree.TreeNode('A');
        TextBinaryTree.TreeNode B = new TextBinaryTree.TreeNode('B');
        TextBinaryTree.TreeNode C = new TextBinaryTree.TreeNode('C');
        TextBinaryTree.TreeNode D = new TextBinaryTree.TreeNode('D');
        TextBinaryTree.TreeNode E = new TextBinaryTree.TreeNode('E');
        TextBinaryTree.TreeNode F = new TextBinaryTree.TreeNode('F');
        TextBinaryTree.TreeNode G = new TextBinaryTree.TreeNode('G');
        TextBinaryTree.TreeNode H = new TextBinaryTree.TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
    //返回这颗树的根节点
    public TreeNode createTree() {
        return root;
    }

    // 前序遍历
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历
    void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.println(root.val + " ");
        inOrder(root.right);
    }

    // 后序遍历
    void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        preOrder(root.left);
        preOrder(root.right);
        System.out.println(root.val + " ");
    }

    public static int nodeSize;

    /**
     * 获取树中节点的个数：遍历思路
     */
    public int count;

    void size(TreeNode root) {//遍历思路
        if (root == null) {
            return;
        } else {
            count++;
        }
        size(root.left);
        size(root.right);
    }

    /**
     * 获取节点的个数：子问题的思路
     *
     * @param root
     * @return
     */
    int size2(TreeNode root) {//子问题思路
        if (root == null) {
            return 0;
        }
        int leftSize = size2(root.left);
        int rightSize = size2(root.right);
        return leftSize + rightSize + 1;
    }


    /*
     获取叶子节点的个数：遍历思路
     */
    public static int leafSize = 0;

    void getLeafNodeCount1(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leafSize++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }

    /*
     获取叶子节点的个数：子问题
     */
    int getLeafNodeCount2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int leftLeaf = getLeafNodeCount2(root.left);
        int rightLeaf = getLeafNodeCount2(root.right);
        return leftLeaf + rightLeaf;
    }

    /*
    获取第K层节点的个数
     */
    //思路：要算第k层的节点数就需要算第左子树的第k-1层的节点数和右子树的k-1层的节点数
    int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        int left = getKLevelNodeCount(root.left, k - 1);
        int right = getKLevelNodeCount(root.right, k - 1);
        return left + right;
    }

    /*
     获取二叉树的高度
     时间复杂度：O(N) 空间复杂度是O(树的高度)
     */
    //思路：算左子树的高度和右子树的高度，返回左子树的高度和右子树高度的最大值，然后+1（根节点的高度）
    int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        int maxHeight = (leftHeight < rightHeight) ? rightHeight : leftHeight;
        return maxHeight + 1;
    }

    // 检测值为value的元素是否存在
    //思路：首先要去遍历一下这个二叉树，从根节点开始，去左子树，如果这个节点val值和val相等
    //     就返回这个节点，左子树没找到就去遍历右子树，然后返回这个val就可以了
    TreeNode find(TreeNode root, char val) {
        if (root == null) {
            return null;
        }
        //如果找到了就返回这个root节点
        if (root.val == val) {
            return root;
        }
        //要有一个返回值取接收这个节点，否则你递归的时候拿到了一个root节点，存放在哪里？？？
        TreeNode leftTree = find(root.left, val);//递归去遍历左子树
        //如果在左子树找到了这个root就返回这个值
        if (leftTree != null) {
            return leftTree;
        }
        TreeNode rightTree = find(root.right, val);//如果没有找到这个值就去遍历右子树
        //如果右子树不为空就说明找到了这个节点，就返回这个节点
        if (rightTree != null) {
            return rightTree;
        }
        return null;
    }

    //层序遍历
    //设计到了顺序，用合适的数据结构,  队列，记录当前弹出的节点，看左右是否为空，不为空就入队列
    //然后打印
    void levelOrder2(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();//链式队列
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.println(cur.val + " ");
            if (cur.left != null) {
                queue.offer(root.left);
            }
            if (cur.right != null) {
                queue.offer(root.right);
            }
        }
    }

    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        return true;
    }

    //给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
    //如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
    //时间复杂度：O（min（M，N））
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //思路：先看头节点是否相同，相同再去判断左子树是否相同，
        // （判断左子树先看左子树的节点是否为空，不为空再判断值是否相同）
        //  再去判断右子树.....
        //一个为空一个不为空
        if (p == null && q != null || p != null && q == null) {
            return false;
        }
        if (p == null && q == null) {//都为空
            return true;
        }
        if (p.val != q.val) {
            return false;
        }
        //pq都不空 且值是一样的
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    //判断一颗树的子树
    //首先判断是不是相同的树  然后判断是不是root的左子树  是不是root的右子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null || subRoot == null) {
            return false;
        }
        //判断是不是相同的树
        if (isSameTree(root, subRoot)) return true;
        //然后去递归root的左子树是不是subroot  或者右子树是不是subroot
        if (isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)) return true;
        return false;
    }

    //反转一颗二叉树
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        //思路：一个节点直接返回根节点，
        // 首先反转根节点的左数和右子树，然后递归反转左子树的左子树和右子树
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    //给定一个二叉树，判断它是否是高度平衡的二叉树。
    //本题中，一棵高度平衡二叉树定义为：
    //一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
    int getHeight(TextBinaryTree.TreeNode root) {//子问题思路
        if (root == null) {
            return 0;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        int max = left < right ? right : left;
        return max + 1;
    }

    public boolean isBalanced(TreeNode root) {//时间复杂度是O（N^2）因为每次求高度都要去递归时间复杂度是O（N）
        //然后每一个节点都要求高度，有n个节点
        if (root == null) {
            return true;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return (Math.abs(left - right) < 2) &&
                isBalanced(root.left) && isBalanced(root.right);
    }

    //字节面试：可不可以再O（n）的时间复杂度内判断是否为高度平衡二叉树
    //思路：如果不平衡，就返回一个负数，在求高度的过程中，如果返回了一个负数，就不是高度平衡的
    int getHeight2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //去求左子树的高度
        int leftHeight = getHeight(root.left);
        if (leftHeight < 0) return -1;
        int rightHeight = getHeight(root.right);
        if (rightHeight < 0) return -1;
        if (Math.abs(leftHeight - rightHeight) <= 1) {
            return Math.max(leftHeight, rightHeight)+1;
        } else {//在求左子树的高度的过程中，左子树的高度-右子树的高度绝对值如果<=1
            //就说明在求左子树高度的过程中，这颗左子树已经不平衡了，返回一个-1，
            //站在头节点的角度，我的左子树给了我一个-1，就说明不平衡，
            // 就不用再去求右子树的高度了
            return -1;
        }
    }

    public boolean isBalanced2(TreeNode root) {
        return getHeight2(root) >= 0;
    }

    //给你一个二叉树的根节点 root ， 检查它是否轴对称
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetricChild(root.left, root.right);
    }

    public boolean isSymmetricChild(TreeNode LeftTree, TreeNode RightTree) {
        if (LeftTree == null && RightTree != null ||
                LeftTree != null && RightTree == null) {
            return false;
        }
        if (LeftTree == null && RightTree == null) return true;
        if (LeftTree.val != RightTree.val) return false;
        return isSymmetricChild(LeftTree.left, RightTree.right)
                && isSymmetricChild(LeftTree.right, RightTree.left);
    }
    //层序遍历
    //层序遍历：涉及到顺序，要用合适的数据结构，队列，当先把头节点入队列，
    // 当队列不为空的时候，就出一个队头数据
    //此时A节点出了，然后判断A的左右是否为空，不空就把A的左入队，右不空就把A的右入队
    //
    public void levelOrder1(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
    //层序遍历（有返回值）
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> ret = new ArrayList<>();
            int size = queue.size();
            while (size != 0) {
                TreeNode cur = queue.poll();
                size--;
                //ret.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(ret);
        }
        return list;
    }
    //给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
    //思路：要么在根节点的左边和右边各一个边，要么全在左边，要么全在右边，要么一个在根节点，另一个在别处
    //如果一个是根节点，就返回根节点就可以了，如果一个在左子树一个在右子树，也是返回根节点
    //如果都是在两边，就去遍历二叉树，遍历到的第一个就是它的公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode leftRet = lowestCommonAncestor(root.left,p,q);
        TreeNode rightRet = lowestCommonAncestor(root.right,p,q);
        if (leftRet != null && rightRet != null) {
            return root;
        }else if (leftRet != null) {
            return leftRet;
        }else if (rightRet != null) {
            return rightRet;
        }
        //都为空的情况，就是没找到
        return null;
    }
    //二叉树的最近公共祖先  思路：要么两个节点一个在左子树，一个在右子树，这个时候的公共祖先就是根节点
    //要么同时在左边，要么同时在右边，，要么一个是另一个的祖先，这个时候公共祖先就是先遍历到的节点
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {//p或者q有一个是根节点
            return root;
        }
        TreeNode leftRet = lowestCommonAncestor(root.left,p,q);
        TreeNode rightRet = lowestCommonAncestor(root.right,p,q);
        if (leftRet != null && rightRet != null) {//左边一个，右边一个
            return root;
        }else if (leftRet != null) {//这个就是右边是空的，就说明节点都在左边，就返回左边第一个拿到的节点
            return leftRet;
        }else if (rightRet != null) {//
            return rightRet;
        }
        return null;
    }
    //给定两个整数数组preorder和inorder其中preorder是二叉树的先序遍历，
    // inorder是同一棵树的中序遍历请构造二叉树并返回其根节点。
    //二叉树的层序遍历   思路：设计到顺序，用合适的数据结构  ，队列
    //先把根节点入队，，定义一个cur，是当前要出队列的元素，然后判断，cur的左边部位空就把左边的元素入队
    //右边不为空，就把右边的元素入队
    public void buildTree2(int[] preorder, int[] inorder) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
          TreeNode cur = queue.poll();
          System.out.println(root.val+ " ");
          if (cur.left != null) {
              queue.offer(cur.left);
          }
          if (cur.right != null) {
              queue.offer(cur.right);
          }
        }
    }
    //二叉树层序遍历：有返回值
    //有返回值，要把每一层的节点放入一个一维数组中，再把每一个一维数组放入一个二维数组中
    //思路：首先要知道每一层有多少个节点，所以要有一个size记录下来当前队列中有多少个节点
    //然后出一个size--，添加到list中，当size-到0，这一层就入队完成
    public List<List<Integer>> levelOrderBottom3(TreeNode root) {
        List<List<Integer>> list= new LinkedList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list1 = new ArrayList<>();
            while (size != 0) {
                TreeNode cur = queue.poll();
                size--;
                //list1.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(list1);
        }
        return list;
    }

    //读入用户输入的一串先序遍历的字符串，根据这个字符串创建一个二叉树
    //如果给定的是一个前序遍历的字符串，就要用前序遍历的方式去处理问题
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            TreeNode root = creatTree(str);
            inorder(root);
        }
    }
    public static int i = 0;
    public static TreeNode creatTree(String str) {
        TreeNode root = null;
        if (str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;//此时的i不会越界，因为有递归的次数
            root.left = creatTree(str);
            root.right = creatTree(str);
        } else {
            i++;
        }
        return root;
    }

    public static TreeNode inorder(TreeNode root) {
        if (root == null) {
            return null;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
        return root;
    }
    //如果这个时候给定一个前驱节点，再去找公共祖先，就变成了两个链表求相交节点
    //但是二叉树没有前驱节点，我们可以用栈来处理，，遍历这颗二叉树，然后去找从根节点
    //到这个p节点的路径，然后从根节点到p节点的路径的所有节点进行入栈，q也一样，
    //然后看谁入栈的节点多，谁就出栈（出差值），出栈的时候去比较是不是公共祖先。
    public boolean getPath(TreeNode root,TreeNode node,
                                   Deque<TreeNode> stack) {
        if (root == null || node == null) {
            return false;
        }
        stack.push(root);
        //放完之后要检查是不是p或q节点
        if (root == node) return true;
        boolean ret1 = getPath(root.left,node,stack);
        if (ret1) return true;
        boolean ret2 = getPath(root.right,node,stack);
        if (ret2) return true;
        //走到这里就说明左右都没找到这个node节点，返回的都是false，就说明不是这个路径
        //就弹出当前入栈的节点
        stack.pop();
        return false;
    }

    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        //1.两个栈当中 存储好数据
        Deque<TreeNode> stack1 = new LinkedList<>();
        getPath(root,p,stack1);
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root,q,stack2);
        //2.判断栈的大小
        int size1 = stack1.size();
        int size2 = stack2.size();
        if (size1 < size2) {
            int size = size2 - size1;
            while (size != 0) {
                stack2.pop();
                size--;
            }
        }else {
            int size = size1 - size2;
            while (size != 0) {
                stack1.pop();
                size--;
            }
        }
        //此时栈中的节点个数是一样的
        //3.比较两个栈中的值是否是相等的
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            if (stack1.peek() != stack2.peek()) {//因为此时存放的是TreeNOde，
                // 里面存放的是地址，可以拿==去判断。
                stack1.pop();
                stack2.pop();
            }else {
                return stack1.peek();
            }
        }
        return null;
    }
    //从中序和前序遍历构造二叉树
    //思路:首先根据前序找出根节点，然后在中序位置找到根节点坐在的位置，定义inbegin是左子树的
    //第一个，inend是最后一个，
    public int t = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }

    public TreeNode buildTreeChild(int[] preorder, int[] inorder,
                              int inbegin, int inend) {
        if (inbegin > inend) return null;
        //TreeNode root = new TreeNode(preorder[i]);
        //在中序遍历中找到根节点
        int rootIndex = findIndex(inorder,inbegin,inend,preorder[i]);
        i++;
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;
    }
    public int findIndex(int[] inorder,int inbegin, int inend,int key){
        for (int j = inbegin; j <=inend; j++) {
            if (inorder[j] == key) {
                return j;
            }
        }
        return -1;
    }
    //根据二叉树创建字符串
    //以前序遍历的方式将二叉树转化为一个由括号和数组组成的字符串，返回这个字符串
    //思路：遇到一棵子树，就+ “(”, 只要由一个子树走完 就+')'，
    //可能出现的情况：左--空， 右--不空，  +“（）”， 左--不空， 右--空 +“）”  都是空，什么都不做
    public String tree2str(TreeNode root) {
        if (root == null) {
            return null;
        }
        //创建一个新的字符串，然后写一个方法，在这个方法中去操作这个字符串，
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }
    public void tree2strChild(TreeNode t,StringBuilder stringBuilder) {
       if (t == null) {
           return;
       }
       //先把根节点加进来，然后再递归去判断左树和右数，再分情况讨论
       stringBuilder.append(t.val);
       if (t.left != null) {
           stringBuilder.append('(');
           tree2strChild(t.left,stringBuilder);
           stringBuilder.append(")");
       }else {
           //左边为空了   讨论右边是否为空
           if (t.right != null) {
               stringBuilder.append("()");
           }else {
               //左右都是空的了
               return;
           }
       }
       if (t.right == null) {//
           return;
       }else {
           stringBuilder.append("(");
           tree2strChild(t.right,stringBuilder);
           stringBuilder.append(")");
       }
    }
    //判断一棵树是不是完全二叉树
    boolean isCompieteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();//尽量用接口去引用
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
               queue.offer(cur.left);//此时不用去判断这个cur的left和right是否为空，因为空不空都要入队
               queue.offer(cur.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if (tmp != null) {
                return false;
            }
        }
        return true;
    }
    //二叉树以非递归的形式去实现前中后序遍历
    //非递归的形式实现前序遍历
    public void preOrderNor(TreeNode root) {
        TreeNode cur = root;
        if (cur == null) {
            return;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val +" ");
                cur = cur.left;
            }
            TreeNode top = stack.poll();
            cur = top.right;
        }
    }
    //中序遍历
    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        TreeNode cur = root;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.poll();
            //ret.add(top.val);
            cur = top.right;
        }
        return ret;
    }
    //非递归的形式实现后序遍历
    public void postOrderNor(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        TreeNode prev = null;//作用：记录打印过的节点
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right == null || top.right == prev) {//加一个||条件，就不会走else循环了
               System.out.println(top.val + " ");
               stack.pop();
               prev = top;//因为此时如果不记录下来当前打印的值，就会进入死循环
                //再peek一下，此时栈中的栈顶元素是B，B的右边不为空，但是B的右边是E，此时已经打印过E了
                //所以应该走if循环而不是走else循环，所以要记录一下打印的结果。
            }else {
                cur = top.right;
            }
        }
        System.out.println();//最后打印完成后就换行
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(root);
                //list.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list;
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            //list.add(cur.val);
            cur = top.right;
        }
        return list;
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();//此时还不能弹出来，因为得看一下右边空不空，右边也是空的，再弹出
            if (top.right == null || top.right == prev) {
                stack.pop();
                System.out.println(cur.val + " ");
                prev = top;
            }else {
                cur = top.right;
            }
        }
        return list;
    }
}

